# 动态规划50题 https://www.bilibili.com/video/BV1aa411f7uT
# 12/50 哪种连续字符串更长
# leetcode第1869题: https://leetcode.cn/problems/longer-contiguous-segments-of-ones-than-zeros/description/
# Date: 2024/11/1
from leetcode import test


def checkZeroOnes(s: str) -> bool:
    """我的答案，本题可以使用简单的模拟方法"""
    n = len(s)
    ml_one = 0  # 记录1最长的长度
    ml_zero = 0  # 记录0最长的长度
    cur = ""  # 记录此前的状态
    cur_len = 0  # 记录当前状态的长度
    for i in range(n):
        if i == 0:
            cur = s[i]

        if s[i] == cur:
            cur_len += 1
            if cur == "1" and ml_one < cur_len:
                ml_one = cur_len
            if cur == "0" and ml_zero < cur_len:
                ml_zero = cur_len
        else:
            cur_len = 1
            cur = s[i]
            if cur == "1" and ml_one < cur_len:
                ml_one = cur_len
            if cur == "0" and ml_zero < cur_len:
                ml_zero = cur_len

    return ml_one > ml_zero


def checkZeroOnes_dp(s: str) -> bool:
    """我的答案，使用动态规划的方法实现"""
    n = len(s)
    if n < 2:
        return s == "1"

    dp = [[0] * n for _ in range(2)]  # 创建一个二维数组，其中dp[0]存放0的长度，dp[1]存放1的最长度
    dp[0][0] = dp[1][0] = 1
    max0 = 0
    max1 = 0
    for i in range(n):
        if s[i - 1] == s[i]:  # 如果和上一个相同则长度+1
            dp[int(s[i])][i] = dp[int(s[i])][i - 1] + 1
        else:
            dp[int(s[i])][i] = 1
        max0 = max(dp[0][i], max0)
        max1 = max(dp[1][i], max1)

    return max1 > max0


if __name__ == '__main__':
    test_example = [{"s": "1101"}, {"s": "111000"}, {"s": "110100010"}, {"s": "101101111000"}, {"s": "01"},
                    {"s": "1"}, ]
    result = [True, False, False, True, False, True]
    test.test_function(checkZeroOnes, test_example, result, times=100)
    test.test_function(checkZeroOnes_dp, test_example, result, times=100)
